package 学习计划.数据结构;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author 会玩的洋洋
 * https://leetcode.cn/problems/merge-intervals/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=cqjfoh6
 */
public class _56_合并区间 {

    /**
     * 执行用时：6ms，内存消耗：46.2MB
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        if (n == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        List<int[]> ret = new ArrayList<>();
        for (int[] interval : intervals) {
            int L = interval[0], R = interval[1];
            if (ret.size() == 0 || ret.get(ret.size() - 1)[1] < L) {
                ret.add(new int[]{L, R});
            } else {
                ret.get(ret.size() - 1)[1] = Math.max(ret.get(ret.size() - 1)[1], R);
            }
        }
        return ret.toArray(new int[ret.size()][]);
    }
}
